package number_operatation.leetcode.medium;

import java.util.Arrays;

/**
 * @author bruin_du
 * @description 数组中数字出现的次数 II
 * @date 2022/6/5 17:25
 **/
public class Offer56II_SingleNumber {
    public int singleNumber(int[] nums) {
        //方法一：排序后取数
        method1(nums);

        //方法二：对每个比特位想加在余3
        return method2(nums);
    }

    private int method2(int[] nums) {
        int[] arr = new int[32];
        for (int num : nums) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] += num & 1;
                num >>>= 1;
                if(num == 0) break;
            }
        }
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            arr[i] %= 3;
            res |= (arr[i] << i);
        }
        return res;
    }

    private int method1(int[] nums) {
        if(nums.length == 1) return nums[0];
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 3; i += 3) {
            if((nums[i] ^ nums[i + 1] ^ nums[i + 2]) != nums[i + 2]) {
                return nums[i];
            }
        }
        return nums[nums.length - 1];
    }
}
